package example.动态规划;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
 * 0 <= k <= input.length <= 10000
 * 0 <= input[i] <= 10000
 * <p>
 * [4,5,1,6,2,7,3,8],4
 * [1,2,3,4]
 */
// NC119 最小的K个数
public class Demo1 {

    /**
     * 这种最简单的就是先排序
     *
     * @param input
     * @param k
     * @return
     */
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(input);
        for (int i = 0; i < input.length; i++) {
            if (i == k) {
                break;
            }
            list.add(input[i]);
        }
        return list;
    }

    public static void main(String[] args) {
        ArrayList<Integer> list = GetLeastNumbers_Solution(new int[]{4, 5, 1, 6, 2, 7, 3, 8}, 4);
        System.out.println(list);
    }
}
